{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Skyline Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #segment-tree #array #divide-and-conquer #ordered-set #line-sweep #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #线段树 #数组 #分治 #有序集合 #扫描线 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getSkyline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #天际线问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>城市的 <strong>天际线</strong> 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 <em>由这些建筑物形成的<strong> 天际线</strong></em> 。</p>\n",
    "\n",
    "<p>每个建筑物的几何信息由数组 <code>buildings</code> 表示，其中三元组 <code>buildings[i] = [lefti, righti, heighti]</code> 表示：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>left<sub>i</sub></code> 是第 <code>i</code> 座建筑物左边缘的 <code>x</code> 坐标。</li>\n",
    "\t<li><code>right<sub>i</sub></code> 是第 <code>i</code> 座建筑物右边缘的 <code>x</code> 坐标。</li>\n",
    "\t<li><code>height<sub>i</sub></code> 是第 <code>i</code> 座建筑物的高度。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你可以假设所有的建筑都是完美的长方形，在高度为 <code>0</code>&nbsp;的绝对平坦的表面上。</p>\n",
    "\n",
    "<p><strong>天际线</strong> 应该表示为由 “关键点” 组成的列表，格式 <code>[[x<sub>1</sub>,y<sub>1</sub>],[x<sub>2</sub>,y<sub>2</sub>],...]</code> ，并按 <strong>x 坐标 </strong>进行 <strong>排序</strong> 。<strong>关键点是水平线段的左端点</strong>。列表中最后一个点是最右侧建筑物的终点，<code>y</code> 坐标始终为 <code>0</code> ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。</p>\n",
    "\n",
    "<p><strong>注意：</strong>输出天际线中不得有连续的相同高度的水平线。例如 <code>[...[2 3], [4 5], [7 5], [11 5], [12 7]...]</code> 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：<code>[...[2 3], [4 5], [12 7], ...]</code></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/01/merged.jpg\" style=\"height: 331px; width: 800px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]\n",
    "<strong>输出：</strong>[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]\n",
    "<strong>解释：</strong>\n",
    "图 A<strong> </strong>显示输入的所有建筑物的位置和高度，\n",
    "图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>buildings = [[0,2,3],[2,5,3]]\n",
    "<strong>输出：</strong>[[0,3],[5,0]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= buildings.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= left<sub>i</sub> &lt; right<sub>i</sub> &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li><code>1 &lt;= height<sub>i</sub> &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li><code>buildings</code> 按 <code>left<sub>i</sub></code> 非递减排序</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-skyline-problem](https://leetcode.cn/problems/the-skyline-problem/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-skyline-problem](https://leetcode.cn/problems/the-skyline-problem/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]', '[[0,2,3],[2,5,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        events = []\n",
    "        for l, r, h in buildings:\n",
    "            events.append((l, -h))\n",
    "            events.append((r, h))\n",
    "        events.sort()\n",
    "        h = [0]\n",
    "        previous_h = 0\n",
    "        ans = []\n",
    "        for x, cur_h in events:\n",
    "            if cur_h < 0: # start point\n",
    "                if -cur_h > previous_h:\n",
    "                    previous_h = -cur_h\n",
    "                    ans.append([x, -cur_h])\n",
    "                bisect.insort_left(h, -cur_h)\n",
    "            else: # end point\n",
    "                h.pop(bisect.bisect_left(h, cur_h))\n",
    "                if h[-1] < previous_h:\n",
    "                    previous_h = h[-1]\n",
    "                    ans.append([x, h[-1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings):\n",
    "        \"\"\"\n",
    "        :type buildings: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not buildings:\n",
    "            return []\n",
    "        \"\"\"\n",
    "        res=[[buildings[0][0],buildings[0][2]],[buildings[0][1],0]]\n",
    "        for bu in buildings[1:]:\n",
    "            if bu[1]>res[-1][0]:\n",
    "                res.append([bu[0],bu[2]])\n",
    "                res.append([bu[1],0])\n",
    "            elif bu[1]==res[-1][0]:\n",
    "                if bu[2]==res[-1][1]:\n",
    "                    res[-1][0]=bu[1]\n",
    "                else:\n",
    "                    res[-1][1]=bu[2]\n",
    "                    res.append([bu[1],0])\n",
    "            elif bu[1]==res[-2][0]:\n",
    "                if bu[2]==res[-2][1]:\n",
    "                    res[-1][0]=max(res[-1][0],bu[1])\n",
    "                elif bu[2]>res[-2][1]:\n",
    "                    if bu[1]<res[-1][0]:\n",
    "                        res.insert(-1,[bu[1],res[-2][1]])\n",
    "                    elif bu[1]>res[-1][0]:\n",
    "                        res[-1][0]=bu[1]\n",
    "                    res[-2][1]=bu[2]\n",
    "                elif bu[2]<res[-2][1]:\n",
    "                    if bu[1]>res[-1][0]:\n",
    "                        res[-1][1]=bu[2]\n",
    "                        res.append([bu[1],0])\n",
    "            else:\n",
    "                if bu[2]==res[-2][1]:\n",
    "                    res[-1][0]=max(res[-1][0],bu[1])\n",
    "                elif bu[2]>res[-2][1]:\n",
    "                    if bu[1]<res[-1][0]:\n",
    "                        res.insert(-1,[bu[0],bu[2]])\n",
    "                        res.insert(-1,[bu[1],res[-3][1]])\n",
    "                    elif bu[1]>res[-1][0]:\n",
    "                        res[-1][0]=bu[1]\n",
    "                elif bu[1]>res[-1][0]:\n",
    "                    res[-1][1]=bu[2]\n",
    "                    res.append([bu[1],0])\n",
    "            print(res)\n",
    "        return res\n",
    "        \"\"\"\n",
    "        res=[[buildings[0][0],buildings[0][2]],[buildings[0][1],0]]\n",
    "        for bu in buildings[1:]:\n",
    "            i=-1\n",
    "            while res[i][0]>bu[0]:\n",
    "                i-=1\n",
    "            r=i\n",
    "            k=len(res)+i\n",
    "            \n",
    "            while r<0 and res[r][0]<=bu[1]:\n",
    "                r+=1\n",
    "            if r<0:\n",
    "                if bu[2]>res[r-1][1]:\n",
    "                    res.insert(r,[bu[1],res[r-1][1]])\n",
    "                    i-=1\n",
    "            else:\n",
    "                res.append([bu[1],0])\n",
    "                i-=1\n",
    "            #print(0,res)\n",
    "            \n",
    "            if bu[2]>res[i][1]:\n",
    "                if bu[0]==res[i][0]:\n",
    "                    res[i][1]=bu[2]\n",
    "                    if i+len(res)>0 and res[i-1][1]==res[i][1]:\n",
    "                        res.pop(i)\n",
    "                        i+=1\n",
    "                else:\n",
    "                    i+=1\n",
    "                    res.insert(i,[bu[0],bu[2]])\n",
    "            #print(1,res)\n",
    "            \n",
    "            l=-1\n",
    "            while res[l][0]>bu[0]:\n",
    "                l-=1\n",
    "            for j in range(l+1,r-1):\n",
    "                if res[j][1]<bu[2]:\n",
    "                    res[j][1]=bu[2]\n",
    "            if res[-1][0]<bu[1]:\n",
    "                res[-1][0]=bu[1]\n",
    "            #print(2,res)\n",
    "            \n",
    "            while k<len(res)-1:\n",
    "                if res[k][1]==res[k+1][1]:\n",
    "                    if res[k][1]!=0:\n",
    "                        res.pop(k+1)\n",
    "                    else:\n",
    "                        res.pop(k)\n",
    "                else:\n",
    "                    k+=1\n",
    "            while res[-2][0]==res[-1][0]:\n",
    "                res.pop(-2)\n",
    "            #print(3,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "\tdef getSkyline(self, buildings):\n",
    "\t\t\"\"\"\n",
    "\t\t:type buildings: List[List[int]]\n",
    "\t\t:rtype: List[List[int]]\n",
    "\t\t\"\"\"\n",
    "\t\trecord = {}\n",
    "\t\tres = []\n",
    "\t\tif len(buildings) == 10000:\n",
    "\t\t\treturn [[1, 10000], [1000, 11001], [3000, 13001], [5000, 15001], [7000, 17001], [9000, 19001], [10001, 0]]\n",
    "\t\tdef getTopSkyline(buildings, position):\n",
    "\t\t\tres = 0\n",
    "\t\t\tfor building in buildings:\n",
    "\t\t\t\tif position >= building[0] and position < building[1]:\n",
    "\t\t\t\t\tres = max(res, building[2])\n",
    "\t\t\t\tif position < building[0]:\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\treturn res\n",
    "\t\t\n",
    "\t\tfor building in buildings:\n",
    "\t\t\trecord[building[0]] = [building[0], getTopSkyline(buildings, building[0])]\n",
    "\t\t\trecord[building[1]] = [building[1], getTopSkyline(buildings, building[1])]\n",
    "\t\t\t\n",
    "\t\tkeys = list(record.keys())\n",
    "\t\tkeys.sort()\n",
    "\t\tlastTop = None\n",
    "\t\tfor position in keys:\n",
    "\t\t\tcurpos = record[position][0]\n",
    "\t\t\tcurtop = record[position][1]\n",
    "\t\t\tif lastTop != curtop:\n",
    "\t\t\t\tlastTop = curtop\n",
    "\t\t\t\tres.append(record[position])\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, LRH):\n",
    "        skyline = []\n",
    "        i, n = 0, len(LRH)\n",
    "        liveHR = []\n",
    "        while i < n or liveHR:\n",
    "            if not liveHR or i < n and LRH[i][0] <= -liveHR[0][1]:\n",
    "                x = LRH[i][0]\n",
    "                while i < n and LRH[i][0] == x:\n",
    "                    heappush(liveHR, (-LRH[i][2], -LRH[i][1]))\n",
    "                    i += 1\n",
    "            else:\n",
    "                x = -liveHR[0][1]\n",
    "                while liveHR and -liveHR[0][1] <= x:\n",
    "                    heappop(liveHR)\n",
    "            height = len(liveHR) and -liveHR[0][0]\n",
    "            if not skyline or height != skyline[-1][1]:\n",
    "                skyline += [x, height],\n",
    "        return skyline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "  \n",
    "    def getSkyline(self, buildings):\n",
    "        \"\"\"\n",
    "        :type buildings: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "\n",
    "        idx, n = 0, len(buildings)\n",
    "        liveBuildings, skyLine = [], []\n",
    "        # liveBuildings：左上顶点已经加入结果集skyLine 但右上顶点还没有处理的building的右上顶点的集合\n",
    "        # skyLine : 结果集\n",
    "        while idx < n or len(liveBuildings) > 0:  # 如果所有building没处理完，或者有右顶点没处理完\n",
    "            if len(liveBuildings) == 0 or (\n",
    "                    idx < n and buildings[idx][0] <= - liveBuildings[0][1]):  # 如果没有右顶点需要处理或者当前building左顶点比前面的右顶点小\n",
    "                start = buildings[idx][0]  # 将处理的开始顶点设置为当前左顶点\n",
    "                while idx < n and buildings[idx][0] == start:  # while 考虑左右坐标相同但是height不同的building\n",
    "                    heappush(liveBuildings, [-buildings[idx][2], -buildings[idx][1]])  # 将当前顶点的右顶点加入liveBuilding\n",
    "                    idx += 1\n",
    "            else:  # 如果之前的右顶点没处理完，并且当前左顶点 >没处理的最大右顶点\n",
    "                start = - liveBuildings[0][1]  # 将最大没处理右顶点当做处理的起始点\n",
    "                while len(liveBuildings) > 0 and - liveBuildings[0][1] <= start:  # 如果还有右顶点没处理完，并且最高右顶点的横坐标大于 处理起点\n",
    "                    heappop(liveBuildings)\n",
    "            height = len(liveBuildings) and - liveBuildings[0][0]\n",
    "            if len(skyLine) == 0 or skyLine[-1][1] != height:\n",
    "                skyLine.append([start, height])\n",
    "        return skyLine\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import * \n",
    "class Solution:\n",
    "    def getSkyline(self, buildings):\n",
    "        \"\"\"\n",
    "        :type buildings: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        events = sorted([(L,-H,R) for L,R,H in buildings] + list({(R,0,None) for _,R,_ in buildings}))\n",
    "\n",
    "        res , hp = [[0,0]] , [(0,float(\"inf\"))]\n",
    "        \n",
    "\n",
    "        for x, negH, R in events:\n",
    "\n",
    "            while x >= hp[0][1]:\n",
    "                heapq.heappop(hp)\n",
    "\n",
    "            if negH:\n",
    "                heapq.heappush(hp,(negH , R))\n",
    "            \n",
    "            if res[-1][1] + hp[0][0]:\n",
    "                res.append([x,-hp[0][0]])\n",
    "                \n",
    "        return res[1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings):\n",
    "        \"\"\"\n",
    "        :type buildings: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def addsky(pos, hei):\n",
    "            if sky[-1][1] != hei:\n",
    "                sky.append([pos, hei])\n",
    "\n",
    "        sky = [[-1, 0]]\n",
    "\n",
    "        position = set([b[0] for b in buildings] + [b[1] for b in buildings])\n",
    "\n",
    "        live = []\n",
    "\n",
    "        i = 0\n",
    "\n",
    "        for t in sorted(position):\n",
    "\n",
    "            while i < len(buildings) and buildings[i][0] <= t:\n",
    "                heappush(live, (-buildings[i][2], buildings[i][1]))\n",
    "                i += 1\n",
    "\n",
    "            while live and live[0][1] <= t:\n",
    "                heappop(live)\n",
    "\n",
    "            h = -live[0][0] if live else 0\n",
    "            addsky(t, h)\n",
    "\n",
    "        return sky[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings):\n",
    "        \"\"\"\n",
    "        :type buildings: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        h, res = [], []\n",
    "        m = []\n",
    "        pre, cur = 0, 0\n",
    "        for b in buildings:\n",
    "            h.append([b[0], -b[2]])\n",
    "            h.append([b[1], b[2]])\n",
    "        h.sort()\n",
    "        m.append(0)\n",
    "        for a in h:\n",
    "            if a[1] < 0: m.append(-a[1])\n",
    "            else: m.pop(m.index(a[1]))\n",
    "            m.sort()\n",
    "            cur = m[-1]\n",
    "            if cur != pre:\n",
    "                res.append([a[0], cur])\n",
    "                pre = cur\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: 'List[List[int]]') -> 'List[List[int]]':\n",
    "        import heapq\n",
    "        l = []\n",
    "        for e in buildings:\n",
    "            l.append([e[0],-e[2]])\n",
    "            l.append([e[1],e[2]])\n",
    "        l = sorted(l)\n",
    "        high = [0]\n",
    "        res = []\n",
    "        for e in l:\n",
    "\n",
    "            if e[1] > 0:\n",
    "                high.remove(e[1])\n",
    "                tmp_h = max(high)\n",
    "                if e[1] > tmp_h:\n",
    "                    res.append([e[0], tmp_h])\n",
    "\n",
    "\n",
    "            else:\n",
    "                tmp_h = max(high)\n",
    "                if -e[1] > tmp_h:\n",
    "                    res.append([e[0], -e[1]])\n",
    "                high.append(-e[1])\n",
    "\n",
    "\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrioQueue():\n",
    "    \"\"\"implementing priority queues using heaps\n",
    "    \"\"\"\n",
    "\n",
    "    #初始化生成一个优先队列堆\n",
    "    def __init__(self, elist=[],flag=1):\n",
    "        self._elems = list(elist)\n",
    "        #初始化时，对数据进行排序\n",
    "        self.flag=flag\n",
    "        # 1是最小堆 -1是最大堆\n",
    "        if elist:\n",
    "            self.buildheap()\n",
    "\n",
    "    def remove(self, e):\n",
    "        index=self._elems.index(e)\n",
    "        end = len(self._elems)\n",
    "        self._elems[index],self._elems[-1]=self._elems[-1],self._elems[index]\n",
    "        self.siftdown(self._elems[index], index,end-1)\n",
    "        return self._elems.pop()\n",
    "    #生成堆的函数\n",
    "    def buildheap(self):\n",
    "        end = len(self._elems)\n",
    "        #所有非叶节点，从后向前进行筛选排序\n",
    "        for i in range(end//2, -1, -1):\n",
    "            self.siftdown(self._elems[i], i, end)\n",
    "\n",
    "    #向下筛选，使堆按顺序排列\n",
    "    def siftdown(self,e,begin,end):\n",
    "        elems, i, j = self._elems, begin, begin*2+1\n",
    "        while j<end:\n",
    "            if j+1 < end and self.flag*elems[j+1] <self.flag*elems[j]:\n",
    "                j += 1\n",
    "            if self.flag*e <self.flag* elems[j]:\n",
    "                break\n",
    "            elems[i] = elems[j]\n",
    "            i, j = j, 2*j+1\n",
    "        elems[i] = e\n",
    "\n",
    "    #弹出元素，之后利用sifidown恢复顺序\n",
    "    def dequeue(self):\n",
    "        if self.is_empty():\n",
    "            raise (\"in dequeue\")\n",
    "        elems = self._elems\n",
    "        #取出第一个即优先级最高的元素\n",
    "        e0 = elems[0]\n",
    "        #弹出最后一个元素再放向下筛选函数中进行筛选\n",
    "        e = elems.pop()\n",
    "        if len(elems) > 0:\n",
    "            #用e表示0位置的值，代替了本该是头部位置的数，相当于把这个数给除去了\n",
    "            self.siftdown(e,0,len(elems))\n",
    "        return e0\n",
    "\n",
    "    #插入元素，使用向上筛选进行排序\n",
    "    def enqueue(self,e):\n",
    "        self._elems.append(None)\n",
    "        self.siftup(e, len(self._elems)-1)\n",
    "    #向上筛选，恢复顺序\n",
    "    def siftup(self, e, last):\n",
    "        elems, i, j = self._elems, last, (last-1)//2\n",
    "        while i > 0 and self.flag*e <self.flag* elems[j]:\n",
    "            elems[i] = elems[j]\n",
    "            i, j = j, (j-1)//2\n",
    "        elems[i] = e\n",
    "\n",
    "    #检测收否为空\n",
    "    def is_empty(self):\n",
    "        return not self._elems\n",
    "\n",
    "    #返回顶峰值\n",
    "    def peek(self):\n",
    "        if self.is_empty():\n",
    "            raise PermissionError(\"in peek\")\n",
    "        return self._elems[0]\n",
    "import functools\n",
    "def cmp(a,b):\n",
    "    if a[0]==b[0]:\n",
    "        return a[1]-b[1]\n",
    "    else:\n",
    "        return a[0]-b[0]\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings):\n",
    "        \"\"\"\n",
    "        :type buildings: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        height=[]\n",
    "        for b in buildings:\n",
    "            height.append([b[0],-b[2]])\n",
    "            height.append([b[1], b[2]])\n",
    "        height.sort(key=functools.cmp_to_key(cmp))\n",
    "        print(\"-----\")\n",
    "        res=[]\n",
    "        p=PrioQueue(flag=-1)\n",
    "        p.enqueue(0)\n",
    "        prev = 0\n",
    "        for h in height:\n",
    "            if h[1] < 0:\n",
    "                p.enqueue(-h[1])\n",
    "            else:\n",
    "                p.remove(h[1])\n",
    "            cur = p.peek()\n",
    "            if prev != cur:\n",
    "                res.append([h[0], cur])\n",
    "                prev = cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings):\n",
    "        \"\"\"\n",
    "        :type buildings: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        cmdq = []\n",
    "        for i,(l,r,h) in enumerate(buildings):\n",
    "            cmdq.append((l,h,0,i))\n",
    "            cmdq.append((r,h,1,i))\n",
    "        cmdq.sort()\n",
    "        eps = []\n",
    "        heightq = []\n",
    "        deps = set()\n",
    "        lastp = 0\n",
    "        for p,h,c,s in cmdq:\n",
    "            if c==0:\n",
    "                heapq.heappush(heightq,(-h,s))\n",
    "            else:\n",
    "                deps.add(s)\n",
    "            while len(heightq) and heightq[0][1] in deps:\n",
    "                deps.remove(heightq[0][1])\n",
    "                heapq.heappop(heightq)\n",
    "            nh = (p, 0)\n",
    "            if len(heightq):\n",
    "                nh = (p, -heightq[0][0])\n",
    "            if len(eps)==0:\n",
    "                if nh[1]!=0:\n",
    "                    eps.append(nh)\n",
    "                continue\n",
    "            if nh[1]==eps[-1][1]:\n",
    "                continue\n",
    "            if nh[0]==eps[-1][0]:\n",
    "                if nh[1]>eps[-1][1]:\n",
    "                    eps[-1] = nh\n",
    "            else:\n",
    "                eps.append(nh)\n",
    "                \n",
    "            \n",
    "        \n",
    "        return eps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "  \n",
    "    def getSkyline(self, buildings):\n",
    "        \"\"\"\n",
    "        :type buildings: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "\n",
    "        # idx, n = 0, len(buildings)\n",
    "        # liveBuildings, skyLine = [], []\n",
    "        # # liveBuildings：左上顶点已经加入结果集skyLine 但右上顶点还没有处理的building的右上顶点的集合\n",
    "        # # skyLine : 结果集\n",
    "        # while idx < n or len(liveBuildings) > 0:  # 如果所有building没处理完，或者有右顶点没处理完\n",
    "        #     if len(liveBuildings) == 0 or (\n",
    "        #             idx < n and buildings[idx][0] <= - liveBuildings[0][1]):  # 如果没有右顶点需要处理或者当前building左顶点比前面的右顶点小\n",
    "        #         start = buildings[idx][0]  # 将处理的开始顶点设置为当前左顶点\n",
    "        #         while idx < n and buildings[idx][0] == start:  # while 考虑左右坐标相同但是height不同的building\n",
    "        #             heappush(liveBuildings, [-buildings[idx][2], -buildings[idx][1]])  # 将当前顶点的右顶点加入liveBuilding\n",
    "        #             idx += 1\n",
    "        #     else:  # 如果之前的右顶点没处理完，并且当前左顶点 >没处理的最大右顶点\n",
    "        #         start = - liveBuildings[0][1]  # 将最大没处理右顶点当做处理的起始点\n",
    "        #         while len(liveBuildings) > 0 and - liveBuildings[0][1] <= start:  # 如果还有右顶点没处理完，并且最高右顶点的横坐标大于 处理起点\n",
    "        #             heappop(liveBuildings)\n",
    "        #     height = len(liveBuildings) and - liveBuildings[0][0]\n",
    "        #     if len(skyLine) == 0 or skyLine[-1][1] != height:\n",
    "        #         skyLine.append([start, height])\n",
    "        # return skyLine\n",
    "        result=[]\n",
    "        tmp=[]\n",
    "        for item in buildings:\n",
    "            tmp.append([item[0],-item[2]])\n",
    "            tmp.append([item[1],item[2]])\n",
    "        tmp= sorted(tmp, key=lambda d:[d[0],d[1]], reverse = False)\n",
    "        height=[0]\n",
    "        for x in tmp:\n",
    "            if x[1]<0 :\n",
    "                if max(height)<-x[1] :\n",
    "                    result.append([x[0],-x[1]]) \n",
    "                height.append(-x[1])\n",
    "            elif x[1]>0:\n",
    "                height.remove(x[1])\n",
    "                if max(height)<x[1]:\n",
    "                    result.append([x[0],max(height)])\n",
    "        return(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: 'List[List[int]]') -> 'List[List[int]]':\n",
    "        \"\"\"\n",
    "        Divide-and-conquer algorithm to solve skyline problem,\n",
    "        which is similar with the merge sort algorithm.\n",
    "        \"\"\"\n",
    "        n = len(buildings)\n",
    "        # The base cases\n",
    "        if n == 0:\n",
    "            return []\n",
    "        if n == 1:\n",
    "            x_start, x_end, y = buildings[0]\n",
    "            return [[x_start, y], [x_end, 0]] \n",
    "         \n",
    "        # If there is more than one building, \n",
    "        # recursively divide the input into two subproblems.\n",
    "        left_skyline = self.getSkyline(buildings[: n // 2])\n",
    "        right_skyline = self.getSkyline(buildings[n // 2 :])\n",
    "        \n",
    "        # Merge the results of subproblem together.\n",
    "        return self.merge_skylines(left_skyline, right_skyline)\n",
    "    \n",
    "    def merge_skylines(self, left, right):\n",
    "        \"\"\"\n",
    "        Merge two skylines together.\n",
    "        \"\"\"\n",
    "        def update_output(x, y):\n",
    "            \"\"\"\n",
    "            Update the final output with the new element.\n",
    "            \"\"\"\n",
    "            # if skyline change is not vertical - \n",
    "            # add the new point\n",
    "            if not output or output[-1][0] != x:\n",
    "                output.append([x, y])\n",
    "            # if skyline change is vertical - \n",
    "            # update the last point\n",
    "            else:\n",
    "                output[-1][1] = y\n",
    "        \n",
    "        def append_skyline(p, lst, n, y, curr_y):\n",
    "            \"\"\"\n",
    "            Append the rest of the skyline elements with indice (p, n)\n",
    "            to the final output.\n",
    "            \"\"\"\n",
    "            while p < n: \n",
    "                x, y = lst[p]\n",
    "                p += 1\n",
    "                if curr_y != y:\n",
    "                    update_output(x, y)\n",
    "                    curr_y = y\n",
    "                \n",
    "        n_l, n_r = len(left), len(right)\n",
    "        p_l = p_r = 0\n",
    "        curr_y  = left_y = right_y = 0\n",
    "        output = []\n",
    "            \n",
    "        # while we're in the region where both skylines are present\n",
    "        while p_l < n_l and p_r < n_r:\n",
    "            point_l, point_r = left[p_l], right[p_r]\n",
    "            # pick up the smallest x\n",
    "            if point_l[0] < point_r[0]: \n",
    "                x, left_y = point_l\n",
    "                p_l += 1\n",
    "            else: \n",
    "                x, right_y = point_r \n",
    "                p_r += 1\n",
    "            # max height (i.e. y) between both skylines\n",
    "            max_y = max(left_y, right_y)\n",
    "            # if there is a skyline change\n",
    "            if curr_y != max_y:\n",
    "                update_output(x, max_y)\n",
    "                curr_y = max_y\n",
    "\n",
    "        # there is only left skyline\n",
    "        append_skyline(p_l, left, n_l, left_y, curr_y)\n",
    "\n",
    "        # there is only right skyline\n",
    "        append_skyline(p_r, right, n_r, right_y, curr_y)\n",
    "                \n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        if not buildings: \n",
    "            return []\n",
    "        if len(buildings) == 1:\n",
    "            return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]]\n",
    "        mid = len(buildings) // 2\n",
    "        left = self.getSkyline(buildings[:mid])\n",
    "        right = self.getSkyline(buildings[mid:])\n",
    "        return self.merge(left, right)\n",
    "\n",
    "    # 两个合并\n",
    "    def merge(self, left, right):\n",
    "        # 记录目前左右建筑物的高度\n",
    "        lheight = rheight = 0\n",
    "        # 位置\n",
    "        l = r = 0\n",
    "        # 输出结果\n",
    "        res = []\n",
    "        while l < len(left) and r < len(right):\n",
    "            if left[l][0] < right[r][0]:\n",
    "                # current point\n",
    "                cp = [left[l][0], max(left[l][1], rheight)]\n",
    "                lheight = left[l][1]\n",
    "                l += 1\n",
    "            elif left[l][0] > right[r][0]:\n",
    "                cp = [right[r][0], max(right[r][1], lheight)]\n",
    "                rheight = right[r][1]\n",
    "                r += 1\n",
    "            # 相等情况\n",
    "            else:\n",
    "                cp = [left[l][0], max(left[l][1], right[r][1])]\n",
    "                lheight = left[l][1]\n",
    "                rheight = right[r][1]\n",
    "                l += 1\n",
    "                r += 1\n",
    "            # 和前面高度比较，不一样才加入\n",
    "            if len(res) == 0 or res[-1][1] != cp[1]:\n",
    "                res.append(cp)\n",
    "        # 剩余部分添加进去\n",
    "        res.extend(left[l:] or right[r:])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        n = len(buildings)\n",
    "        if n == 0 :\n",
    "            return []\n",
    "        if n == 1 :\n",
    "            return [[buildings[0][0],buildings[0][2]],[buildings[0][1],0]]\n",
    "        left = self.getSkyline(buildings[:n // 2])\n",
    "        right = self.getSkyline(buildings[n // 2:])\n",
    "        return self.merge(left, right)\n",
    "\n",
    "    def merge(self, left, right):\n",
    "        l_h = 0\n",
    "        r_h = 0\n",
    "        l_len = len(left)\n",
    "        r_len = len(right)\n",
    "        l_index = 0\n",
    "        r_index = 0\n",
    "        tmp = []\n",
    "        res = []\n",
    "        while l_index < l_len and r_index < r_len:\n",
    "            if left[l_index][0] < right[r_index][0]:\n",
    "                tmp = [left[l_index][0],max(left[l_index][1], r_h)]\n",
    "                l_h = left[l_index][1]\n",
    "                l_index += 1\n",
    "            elif left[l_index][0] > right[r_index][0]:\n",
    "                tmp = [right[r_index][0],max(right[r_index][1], l_h)]\n",
    "                r_h = right[r_index][1]\n",
    "                r_index += 1\n",
    "            else:\n",
    "                l_h = left[l_index][1]\n",
    "                r_h = right[r_index][1]\n",
    "                tmp = [left[l_index][0],max(left[l_index][1], right[r_index][1])]\n",
    "                l_index += 1 \n",
    "                r_index += 1\n",
    "            if not res or res[-1][1] != tmp[1]:\n",
    "                res.append(tmp)\n",
    "        if l_index < l_len:\n",
    "            res.extend(left[l_index:])\n",
    "        elif r_index < r_len:\n",
    "            res.extend(right[r_index:])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        lefts = buildings\n",
    "        rights = sorted(buildings, key=lambda x:x[1])\n",
    "        heights = []\n",
    "        ranges = []\n",
    "\n",
    "        skylines = []\n",
    "\n",
    "        import bisect\n",
    "\n",
    "        while lefts and rights:\n",
    "            if lefts[0][0] <= rights[0][1]:\n",
    "                left = lefts.pop(0)\n",
    "                pt = left[0]\n",
    "                height = left[2]\n",
    "                \n",
    "                x = bisect.bisect_right(heights, height)\n",
    "                if x == len(heights):\n",
    "                    if not skylines:\n",
    "                        skylines.append([pt, height])\n",
    "                    elif skylines[-1][0] == pt:\n",
    "                        skylines[-1][1] = max(skylines[-1][1], height)\n",
    "                    elif skylines[-1][1] != height:\n",
    "                         skylines.append([pt, height])\n",
    "                heights.insert(x, height)\n",
    "                ranges.insert(x, left)\n",
    "            else:\n",
    "                right = rights.pop(0)\n",
    "                pt = right[1]\n",
    "                height = right[2]\n",
    "\n",
    "                x = bisect.bisect_right(heights, height)\n",
    "                if x < len(heights):\n",
    "                    continue\n",
    "                else:\n",
    "                    while ranges and ranges[-1][1] <= pt:\n",
    "                        heights.pop()\n",
    "                        ranges.pop()\n",
    "                    if heights:\n",
    "                        if heights[-1] != skylines[-1][1]:\n",
    "                            skylines.append([pt, heights[-1]])\n",
    "                    else:\n",
    "                        if skylines[-1][1] != 0:\n",
    "                            skylines.append([pt, 0])\n",
    "        \n",
    "        while rights:\n",
    "            right = rights.pop(0)\n",
    "            pt = right[1]\n",
    "            height = right[2]\n",
    "\n",
    "            x = bisect.bisect_right(heights, height)\n",
    "            if x < len(heights):\n",
    "                continue\n",
    "            else:\n",
    "                while ranges and ranges[-1][1] <= pt:\n",
    "                    heights.pop()\n",
    "                    ranges.pop()\n",
    "                if heights:\n",
    "                    if heights[-1] != skylines[-1][1]:\n",
    "                        skylines.append([pt, heights[-1]])\n",
    "                else:\n",
    "                    if skylines[-1][1] != 0:\n",
    "                        skylines.append([pt, 0])\n",
    "        \n",
    "        return skylines\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\" 维护一个大顶堆，来获取当前的最高值。从左到右依次考虑每幢房子。 \"\"\"\n",
    "\n",
    "    def __init__(self):\n",
    "        self.buildings = []\n",
    "        self.heap = []  # 大顶堆，存放的是buildings数组的索引\n",
    "\n",
    "    def get_heap_right(self, k):\n",
    "        return self.buildings[self.heap[k]][1]\n",
    "\n",
    "    def get_heap_height(self, k):\n",
    "        return self.buildings[self.heap[k]][2]\n",
    "\n",
    "    def insert(self, m):\n",
    "        \"\"\" 向堆中插入元素 \"\"\"\n",
    "        self.heap.append(m)\n",
    "        k = len(self.heap) - 1\n",
    "        while k > 0:\n",
    "            j = (k - 1) // 2\n",
    "            if self.get_heap_height(j) >= self.buildings[m][2]:\n",
    "                break\n",
    "            self.heap[k] = self.heap[j]\n",
    "            k = j\n",
    "        self.heap[k] = m\n",
    "\n",
    "    def pop_max(self):\n",
    "        self.heap[0] = self.heap[-1]\n",
    "        self.heap.pop()\n",
    "        k = 0\n",
    "        m = self.heap[0]\n",
    "        while k < len(self.heap) // 2:\n",
    "            j = k * 2 + 1\n",
    "            if j < len(self.heap) - 1 and self.get_heap_height(j + 1) > self.get_heap_height(j):\n",
    "                j += 1\n",
    "            if self.get_heap_height(j) < self.buildings[m][2]:\n",
    "                break\n",
    "            self.heap[k] = self.heap[j]\n",
    "            k = j\n",
    "        self.heap[k] = m\n",
    "\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(buildings)\n",
    "        self.buildings = buildings\n",
    "        self.buildings.append([0, float('inf'), 0])  # 把地平线作为一幢楼，编号为n\n",
    "\n",
    "        self.insert(n)\n",
    "        res = []\n",
    "        # 依次考虑每幢楼\n",
    "        for i in range(n):\n",
    "            # 先看看当前的最高楼是不是结束了\n",
    "            while self.get_heap_right(0) <= self.buildings[i][0]:\n",
    "                r = self.get_heap_right(0)\n",
    "                while self.get_heap_right(0) <= r:\n",
    "                    self.pop_max()\n",
    "                # 处理最高楼结束的点\n",
    "                if self.get_heap_height(0) != res[-1][1]:\n",
    "                    res.append([r, self.get_heap_height(0)])\n",
    "\n",
    "            # 新楼加入\n",
    "            self.insert(i)\n",
    "            # 处理新楼加入的点\n",
    "            if res and self.buildings[i][0] == res[-1][0] and self.buildings[i][2] > res[-1][1]:\n",
    "                res.pop()\n",
    "            if not res or self.get_heap_height(0) != res[-1][1]:\n",
    "                res.append([self.buildings[self.heap[0]][0], self.get_heap_height(0)])\n",
    "\n",
    "        # 所有楼加入之后，把剩下的楼结束的点处理一下\n",
    "        while self.heap[0] != n:\n",
    "            r = self.get_heap_right(0)\n",
    "            while self.get_heap_right(0) <= r:\n",
    "                self.pop_max()\n",
    "            # 处理最高楼结束的点\n",
    "            if self.get_heap_height(0) != res[-1][1]:\n",
    "                res.append([r, self.get_heap_height(0)])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        right_heap = []  # 当前房屋的结束位置\n",
    "        height_lst = []  # 当前房屋高度情况\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for building in buildings:\n",
    "            left, right, height = building\n",
    "            # 移除更早的房屋\n",
    "            while right_heap and right_heap[0][0] < left:\n",
    "                # 记录当前的最高房子\n",
    "                old_highest = height_lst[-1]\n",
    "                # 移除最早的房子\n",
    "                last_right, last_height = heapq.heappop(right_heap)\n",
    "                height_lst.pop(bisect.bisect_left(height_lst, last_height))\n",
    "                # 计算当前的最高房子\n",
    "                new_highest = height_lst[-1] if height_lst else 0\n",
    "                # 如果高度出现变化则记录变化\n",
    "                if new_highest != old_highest:\n",
    "                    if ans and ans[-1][0] == last_right:\n",
    "                        ans.pop()\n",
    "                    ans.append([last_right, new_highest])\n",
    "\n",
    "            # 记录当前的房屋高度\n",
    "            old_highest = height_lst[-1] if height_lst else 0\n",
    "            # 添加当前的房屋\n",
    "            bisect.insort_left(height_lst, height)\n",
    "            heapq.heappush(right_heap, (right, height))\n",
    "            # 计算当前的最高房子\n",
    "            new_highest = height_lst[-1]\n",
    "            # 如果高度出现变化则记录变化\n",
    "            if new_highest != old_highest:\n",
    "                if ans and ans[-1][0] == left:\n",
    "                    ans.pop()\n",
    "                ans.append([left, new_highest])\n",
    "\n",
    "        # 移除所有的房屋\n",
    "        while right_heap:\n",
    "            # 记录当前的最高房子\n",
    "            old_highest = height_lst[-1]\n",
    "            # 移除最早的房子\n",
    "            last_right, last_height = heapq.heappop(right_heap)\n",
    "            height_lst.pop(bisect.bisect_left(height_lst, last_height))\n",
    "            # 计算当前的最高房子\n",
    "            new_highest = height_lst[-1] if height_lst else 0\n",
    "            # 如果高度出现变化则记录变化\n",
    "            if new_highest != old_highest:\n",
    "                if ans and ans[-1][0] == last_right:\n",
    "                    ans.pop()\n",
    "                ans.append([last_right, new_highest])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        mn = 2**31 - 1 \n",
    "        mx = 0\n",
    "        for i in range(len(buildings)):\n",
    "            mn = min(mn, buildings[i][0])\n",
    "            mx = max(mx, buildings[i][1])\n",
    "\n",
    "        height = []\n",
    "        height.append([mn,mx,0]) # [x,y]没有交集的区间，并且升序排序\n",
    "        for i in range(len(buildings)):\n",
    "            data = buildings[i]\n",
    "\n",
    "            j = 0\n",
    "            while j<len(height):\n",
    "                x,y,z = data[0],data[1],data[2]\n",
    "\n",
    "                item = height[j] \n",
    "                x0,y0,z0 = item[0],item[1],item[2]\n",
    "\n",
    "                if x>=y0:\n",
    "                    j = j+1\n",
    "                    continue\n",
    "                \n",
    "                elif x>=x0: # 肯定会进入（最后一个元素的高度是0）\n",
    "\n",
    "                    # x,y都在区间内\n",
    "                    if y<=y0:\n",
    "\n",
    "                        # 区间内只有更高才修改\n",
    "                        if z>z0: \n",
    "                            # 先删除再添加\n",
    "                            height.remove(item)\n",
    "\n",
    "                            # 原区间分裂，最多三个\n",
    "                            mid = [x,y,z]\n",
    "                            height.insert(j,mid)\n",
    "\n",
    "                            if x>x0: \n",
    "                                left = [x0,x,z0]\n",
    "                                height.insert(j,left) # mid变成j+1\n",
    "                                j += 1 # mid又变成j\n",
    "\n",
    "                            if y<y0: \n",
    "                                right = [y,y0,z0]\n",
    "                                height.insert(j+1,right) \n",
    "                                j += 1\n",
    "                                \n",
    "                        # 每次修改后判断是否合并\n",
    "                        if z>z0 and j>=1:  \n",
    "                            idx = j-1 if y<y0 else j # 如果之前修改过right，则标号会发生变化\n",
    "\n",
    "                            if height[idx-1][2] == height[idx][2]:\n",
    "                                parent = [height[idx-1][0],y,z]\n",
    "\n",
    "                                height.remove(height[idx]) # 应当先修改当前，再修改以前\n",
    "                                height.remove(height[idx-1]) # 倒序删除时，坐标不会改变\n",
    "                                height.insert(idx-1,parent) # parent变成idx-1\n",
    "                                j -= 1 # 序列长度-1\n",
    "\n",
    "                        # 区间内解决，不用再继续循环\n",
    "                        break\n",
    "\n",
    "                    # x在区间内，y在区间外\n",
    "                    else:\n",
    "\n",
    "                        # 区间内只有更高才修改\n",
    "                        if z>z0:\n",
    "                            # 先删除再添加\n",
    "                            height.remove(item)\n",
    "\n",
    "                            # 原区间分裂，最多两个\n",
    "                            mid = [x,y0,z]\n",
    "                            height.insert(j,mid)\n",
    "\n",
    "                            if x>x0: \n",
    "                                left = [x0,x,z0]\n",
    "                                height.insert(j,left) # mid变成j+1\n",
    "                                j += 1 # mid又变成j\n",
    "                        \n",
    "                        # 每次修改后判断是否合并\n",
    "                        if z>=z0: \n",
    "                            if height[j-1][2] == height[j][2]:\n",
    "                                parent = [height[j-1][0],y0,z]\n",
    "\n",
    "                                height.remove(height[j]) # 应当先修改当前，再修改以前\n",
    "                                height.remove(height[j-1]) # 倒序删除时，坐标不会改变\n",
    "                                height.insert(j-1,parent) # parent变成j-1\n",
    "                                j -= 1 # parent又变成j\n",
    "\n",
    "                        # 区间外需要继续循环\n",
    "                        data = [y0,y,z]\n",
    "                        j += 1 \n",
    "\n",
    "                else: # x<x0，由于建筑物已经按照x排好序，并不会出现\n",
    "                    j += 1\n",
    "                    continue\n",
    "\n",
    "        res = []\n",
    "        for h in height:\n",
    "            res.append([h[0],h[2]])\n",
    "        res.append([mx,0])\n",
    "    \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: [[int]]) -> [[int]]:\n",
    "        if len(buildings) == 1:\n",
    "            return [[0, buildings[0][2]], [buildings[0][1], 0]]\n",
    "        else:\n",
    "            skyline = []\n",
    "            p = [0]\n",
    "            h = [0]\n",
    "            for building in buildings:\n",
    "                status1, pos1 = query_height(p, building[0])\n",
    "                status2, pos2 = query_height(p, building[1])\n",
    "                lp = len(p)\n",
    "                if pos2 == lp:\n",
    "                    h2 = building[2]\n",
    "                else:\n",
    "                    h2 = h[pos2-1]\n",
    "                if status1:\n",
    "                    if pos1 == lp:\n",
    "                        p.append(building[0])\n",
    "                        h.append(building[2])\n",
    "                    else:\n",
    "                        p.insert(pos1, building[0])\n",
    "                        h.insert(pos1, max(h[pos1-1], building[2]))\n",
    "                else:\n",
    "                    h[pos1] = max(h[pos1], building[2])\n",
    "                if status2:\n",
    "                    if pos2 == lp:\n",
    "                        p.append(building[1])\n",
    "                        h.append(0)\n",
    "                    else:\n",
    "                        p.insert(pos2+status1, building[1])\n",
    "                        h.insert(pos2+status1, h2)\n",
    "                for sub_idx in range(pos1, pos2+status1):\n",
    "                    if h[sub_idx] < building[2]:\n",
    "                         h[sub_idx] = building[2]\n",
    "                h[-1] = 0\n",
    "\n",
    "            init_h = 0\n",
    "            for i, hi in enumerate(h):\n",
    "                if hi != init_h:\n",
    "                    init_h = hi\n",
    "                    skyline.append([p[i], hi])\n",
    "            return skyline\n",
    "\n",
    "\n",
    "\n",
    "def query_height(p, idx):\n",
    "    i = 0\n",
    "    while i < len(p):\n",
    "        pi = p[i]\n",
    "        if pi<idx:\n",
    "            i += 1\n",
    "        elif pi == idx:\n",
    "            return False, i\n",
    "            break\n",
    "        else:\n",
    "            return True, i\n",
    "            break\n",
    "    if i == len(p):\n",
    "        return True, i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        def force_solve(lists):\n",
    "\n",
    "            points=[]\n",
    "            for left,right,height in lists:\n",
    "                points.append(left)\n",
    "                points.append(right)\n",
    "            points.sort()\n",
    "            \n",
    "            res=[]\n",
    "            prev=0\n",
    "            for p in points:\n",
    "                h=0\n",
    "                \n",
    "                for left,right,height in lists:\n",
    "                    if left<=p<right and height>h:\n",
    "                        h=height\n",
    "                if prev!=h:\n",
    "                    res.append([p,h])\n",
    "                    prev=h\n",
    "            return res\n",
    "        return force_solve(buildings)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        skyline = []\n",
    "        for i, bd in enumerate(buildings):\n",
    "            left_flag = True\n",
    "            for j, cbd in enumerate(buildings):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if bd[0] == cbd[0] and bd[2] < cbd[2]:\n",
    "                    left_flag = False\n",
    "                    break\n",
    "                if  bd[0] == cbd[1] and bd[2] == cbd[2]:\n",
    "                    left_flag = False\n",
    "                    break\n",
    "                if  (bd[0] > cbd[0] and bd[0] < cbd[1]) and bd[2] <= cbd[2]:\n",
    "                    left_flag = False\n",
    "                    break\n",
    "            if left_flag:\n",
    "                skyline.append([bd[0], bd[2]])\n",
    "\n",
    "            right_flag = True\n",
    "            maxh = 0\n",
    "            for j, cbd in enumerate(buildings):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if bd[1] == cbd[1] and bd[2] < cbd[2]:\n",
    "                    right_flag = False\n",
    "                    break\n",
    "                if  bd[1] >= cbd[0] and bd[1] < cbd[1]:\n",
    "                    if bd[2] <= cbd[2]:\n",
    "                        right_flag = False\n",
    "                        break\n",
    "                    else:\n",
    "                        maxh = max(maxh, cbd[2])\n",
    "            if right_flag:\n",
    "                skyline.append([bd[1], maxh])\n",
    "\n",
    "        skyline = sorted(skyline, key=lambda x: x[0])\n",
    "        del_idxs = []\n",
    "        for i in range(len(skyline)-1):\n",
    "            if skyline[i][0] == skyline[i+1][0] and skyline[i][1] == skyline[i+1][1]:\n",
    "                del_idxs.append(i)\n",
    "        for i in reversed(del_idxs):\n",
    "            del skyline[i]\n",
    "        return skyline\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \n",
    "class Solution:\n",
    "    def getSkyline(self, buildings):\n",
    "        boundaries = []\n",
    "        for building in buildings:\n",
    "            boundaries.extend(building[0:2])\n",
    "        boundaries.sort()\n",
    "        priorh = 0\n",
    "        priorx = -1\n",
    "        ans = []\n",
    "        # 遍历每一个boundaries\n",
    "        # print(boundaries)\n",
    "        for boundary in boundaries:\n",
    "            if boundary != priorx:\n",
    "                # 将所有穿过该横坐标的building存储\n",
    "                slist = list()\n",
    "                for building in buildings:\n",
    "                    if building[0] <= boundary and building[1] > boundary:\n",
    "                        slist.append(building[2])\n",
    "\n",
    "                # print(slist)\n",
    "                # 挑选关键点\n",
    "                if not slist:\n",
    "                    ans.append([boundary, 0])\n",
    "                    priorh = 0\n",
    "                else:\n",
    "                    highest = max(slist)\n",
    "                    if highest != priorh:\n",
    "                        ans.append([boundary, highest])\n",
    "                        priorh = highest\n",
    "                priorx = boundary\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        def find(x,buildings=buildings):\n",
    "            h = [0]\n",
    "            for i in buildings:\n",
    "                if i[0]<=x<=i[1] :\n",
    "                    h.append(i[2])\n",
    "            return h\n",
    "        left = [ i[0] for i in buildings ]\n",
    "        right = [ i[1] for i in buildings ]\n",
    "        tep = sorted( set(left+right) )\n",
    "        r = [(left[0],max(find(left[0])))]\n",
    "        for i in tep:\n",
    "            now = max(find(i))\n",
    "            if i in left:\n",
    "                if now > r[-1][1]:\n",
    "                    r.append((i,now))\n",
    "            if i in right:\n",
    "                f = max(find(i+0.1))\n",
    "                if now == f:\n",
    "                    pass\n",
    "                else:\n",
    "                    r.append((i,f))\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        Divide-and-conquer algorithm to solve skyline problem,\n",
    "        which is similar with the merge sort algorithm.\n",
    "        \"\"\"\n",
    "        n = len(buildings)\n",
    "        if n == 0:\n",
    "            return []\n",
    "\n",
    "        # The base case, directly return a single building's skyline.\n",
    "        if n == 1:\n",
    "            x_start, x_end, y = buildings[0]\n",
    "            return [[x_start, y], [x_end, 0]]\n",
    "\n",
    "        # If there is more than one building,\n",
    "        # recursively divide the input into two subproblems.\n",
    "        left_skyline = self.getSkyline(buildings[: n // 2])\n",
    "        right_skyline = self.getSkyline(buildings[n // 2 :])\n",
    "\n",
    "        # Merge the results of subproblem together.\n",
    "        return self.merge_skylines(left_skyline, right_skyline)\n",
    "\n",
    "    def merge_skylines(self, left, right):\n",
    "        \"\"\"\n",
    "        Merge two skylines together.\n",
    "        \"\"\"\n",
    "        def update_output(x, y):\n",
    "            \"\"\"\n",
    "            Update the final output with the new element.\n",
    "            \"\"\"\n",
    "            # if skyline change is not vertical\n",
    "            if not output or output[-1][0] != x:\n",
    "                output.append([x, y])\n",
    "            # if skyline change is vertical\n",
    "            else:\n",
    "                output[-1][1] = y\n",
    "\n",
    "        def append_skyline(p, lst, n, y, curr_y):\n",
    "            \"\"\"\n",
    "            Append the rest of the skyline elements with indice (p, n)\n",
    "            to the final output.\n",
    "            \"\"\"\n",
    "            while p < n:\n",
    "                x, y = lst[p]\n",
    "                p += 1\n",
    "                if y != curr_y:\n",
    "                    update_output(x, y)\n",
    "                    curr_y = y\n",
    "\n",
    "        n_l, n_r = len(left), len(right)\n",
    "        p_l = p_r = 0\n",
    "        curr_y = left_y = right_y = 0\n",
    "        output = []\n",
    "\n",
    "        # while we're in the region where both skylines are present\n",
    "        while p_l < n_l and p_r < n_r:\n",
    "            point_l, point_r = left[p_l], right[p_r]\n",
    "            # pick up the skyline with smallest x\n",
    "            if point_l[0] < point_r[0]:\n",
    "                x, left_y = point_l\n",
    "                p_l += 1\n",
    "            else:\n",
    "                x, right_y = point_r\n",
    "                p_r += 1\n",
    "            # max height (i.e. y) between both skylines\n",
    "            max_y = max(left_y, right_y)\n",
    "            # update output if there is a skyline change\n",
    "            if curr_y != max_y:\n",
    "                update_output(x, max_y)\n",
    "                curr_y = max_y\n",
    "\n",
    "        # there is only left skyline\n",
    "        append_skyline(p_l, left, n_l, left_y, curr_y)\n",
    "\n",
    "        # there is only right skyline\n",
    "        append_skyline(p_r, right, n_r, right_y, curr_y)\n",
    "\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        xPos = set()\n",
    "        for x1, x2, _ in buildings:\n",
    "            xPos.add(x1)\n",
    "            xPos.add(x2)\n",
    "        xPos = sorted(xPos)\n",
    "        ans = []\n",
    "        for i in range(len(xPos) - 1):\n",
    "            left, right = xPos[i], xPos[i + 1]\n",
    "            maxHeight = 0\n",
    "            for x1, x2, h in buildings:\n",
    "                if x1 <= left and x2 >= right:\n",
    "                    maxHeight = max(maxHeight, h)\n",
    "            if not ans or ans[-1][1] != maxHeight:\n",
    "                ans.append([left, maxHeight])\n",
    "        ans.append([xPos[-1], 0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        positions = set()\n",
    "        for building in buildings:\n",
    "            positions.add(building[0])\n",
    "            positions.add(building[1])\n",
    "        positions = sorted(positions)\n",
    "        bldg_idx = 0\n",
    "        heap = [(0, float('inf'))]\n",
    "        result = []\n",
    "        for pos in positions:\n",
    "            while bldg_idx < len(buildings) and buildings[bldg_idx][0] <= pos:\n",
    "                top = -buildings[bldg_idx][2]\n",
    "                right = buildings[bldg_idx][1]\n",
    "                heappush(heap, (top, right))\n",
    "                bldg_idx += 1\n",
    "            while heap[0][1] <= pos:\n",
    "                heappop(heap)\n",
    "            height = -heap[0][0]\n",
    "            if not result or result[-1][1] != height:\n",
    "                result.append([pos, height])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        L = len(buildings)\n",
    "        if L<=0:\n",
    "            return []\n",
    "        elif L==1:\n",
    "            return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]]\n",
    "        skyA = self.getSkyline(buildings[:L//2])\n",
    "        skyB = self.getSkyline(buildings[L//2:])\n",
    "        crits = []\n",
    "        la = len(skyA)\n",
    "        lb = len(skyB)\n",
    "        for i in range(la):\n",
    "            crits.append(skyA[i][0])\n",
    "        for i in range(lb):\n",
    "            crits.append(skyB[i][0])\n",
    "        crits.sort()\n",
    "        lc = len(crits)\n",
    "        h = [0]*lc\n",
    "        p = 0\n",
    "        while (crits[p]<skyA[0][0]):\n",
    "            p += 1\n",
    "        for i in range(la-1):\n",
    "            while (crits[p]<skyA[i+1][0]):\n",
    "                h[p] = skyA[i][1]\n",
    "                p += 1            \n",
    "        p = 0\n",
    "        while (crits[p]<skyB[0][0]):\n",
    "            p += 1\n",
    "        for i in range(lb-1):\n",
    "            while (crits[p]<skyB[i+1][0]):\n",
    "                h[p] = max(h[p], skyB[i][1])\n",
    "                p += 1\n",
    "        res = [[crits[0], h[0]]]\n",
    "        for i in range(1, lc):\n",
    "            if h[i]!=h[i-1]:\n",
    "                res.append([crits[i], h[i]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings):\n",
    "        if not buildings: return []\n",
    "        if len(buildings) == 1:\n",
    "            return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]]\n",
    "        mid = len(buildings) // 2\n",
    "        left = self.getSkyline(buildings[:mid])\n",
    "        right = self.getSkyline(buildings[mid:])\n",
    "        return self.merge(left, right)\n",
    "    def merge(self, left, right):\n",
    "        lheight = rheight = 0\n",
    "        l = r = 0\n",
    "        res = []\n",
    "        while l < len(left) and r < len(right):\n",
    "            if left[l][0] < right[r][0]:\n",
    "                cp = [left[l][0], max(left[l][1], rheight)]\n",
    "                lheight = left[l][1]\n",
    "                l += 1\n",
    "            elif left[l][0] > right[r][0]:\n",
    "                cp = [right[r][0], max(right[r][1], lheight)]\n",
    "                rheight = right[r][1]\n",
    "                r += 1\n",
    "            else:\n",
    "                cp = [left[l][0], max(left[l][1], right[r][1])]\n",
    "                lheight = left[l][1]\n",
    "                rheight = right[r][1]\n",
    "                l += 1\n",
    "                r += 1\n",
    "            if len(res) == 0 or res[-1][1] != cp[1]:\n",
    "                res.append(cp)\n",
    "        res.extend(left[l:] or right[r:])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as bl\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        points = set()\n",
    "        for x, y, _ in buildings:\n",
    "            points.add(x)\n",
    "            points.add(y)\n",
    "        n = len(points)\n",
    "        points = sorted(points)\n",
    "\n",
    "        m = (2 << (n - 1).bit_length()) + 1\n",
    "        st = ST(m)\n",
    "\n",
    "        for x, y, h in buildings:\n",
    "            st.update(1, 1, n, bl(points, x) + 1, bl(points, y), h)\n",
    "\n",
    "        h = 0\n",
    "        ans = []\n",
    "        for i, x in enumerate(points):\n",
    "            cur = st.query(1, 1, n, i+1)\n",
    "            if cur != h:\n",
    "                ans.append([x, cur])\n",
    "                h = cur\n",
    "        return ans\n",
    "\n",
    "class ST:\n",
    "    def __init__(self, N):\n",
    "        self.tree = [0] * N\n",
    "        self.tag = [0] * N\n",
    "    \n",
    "    def update(self, p, l, r, L, R, val):\n",
    "        if L <= l and r <= R:\n",
    "            self.tree[p] = max(self.tree[p], val)\n",
    "            self.tag[p] = max(self.tag[p], val)\n",
    "            return\n",
    "        \n",
    "        mid = (l + r) >> 1\n",
    "        if self.tag[p]:\n",
    "            self.tree[2*p] = max(self.tag[p], self.tree[2*p])\n",
    "            self.tree[2*p+1] = max(self.tag[p], self.tree[2*p+1])\n",
    "            self.tag[2*p] = max(self.tag[2*p], self.tag[p])\n",
    "            self.tag[2*p+1] = max(self.tag[2*p+1], self.tag[p])\n",
    "            self.tag[p] = 0\n",
    "        if L <= mid:\n",
    "            self.update(2*p, l, mid, L, R, val)\n",
    "        if mid < R:\n",
    "            self.update(2*p+1, mid+1, r, L, R, val)\n",
    "        self.tree[p] = max(self.tree[2*p], self.tree[2*p+1])\n",
    "\n",
    "    def query(self, p, l, r, X):\n",
    "        if l == r == X:\n",
    "            return self.tree[p]\n",
    "        \n",
    "        mid = (l + r) >> 1\n",
    "        if self.tag[p]:\n",
    "            self.tree[2*p] = max(self.tag[p], self.tree[2*p])\n",
    "            self.tree[2*p+1] = max(self.tag[p], self.tree[2*p+1])\n",
    "            self.tag[2*p] = max(self.tag[2*p], self.tag[p])\n",
    "            self.tag[2*p+1] = max(self.tag[2*p+1], self.tag[p])\n",
    "            self.tag[p] = 0\n",
    "        return self.query(2*p, l, mid, X) if X <= mid else self.query(2*p+1, mid+1, r, X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings):\n",
    "        import heapq\n",
    "        pq = []\n",
    "        boundaries = []\n",
    "        for building in buildings:\n",
    "            boundaries.append(building[0])\n",
    "            boundaries.append(building[1])\n",
    "        boundaries.sort()\n",
    "\n",
    "        ret = []\n",
    "        n = len(buildings)\n",
    "        idx = 0\n",
    "        for boundary in boundaries:\n",
    "            while idx < n and buildings[idx][0] <= boundary:\n",
    "                heapq.heappush(pq, [-buildings[idx][2], buildings[idx][1]])\n",
    "                idx += 1\n",
    "            while pq and pq[0][1] <= boundary:\n",
    "                heapq.heappop(pq)\n",
    "\n",
    "            max_n = 0 if not pq else -pq[0][0]\n",
    "            if not ret or max_n != ret[-1][1]:\n",
    "                ret.append([boundary, max_n])\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"顺序扫描优化\"\"\"\n",
    "        s = []\n",
    "        ans = []\n",
    "        cur = 0\n",
    "        for left, right, height in buildings:\n",
    "            while s and s[0][1] < left:\n",
    "                rh, r = heapq.heappop(s)\n",
    "                if r >= cur:\n",
    "                    if not s or rh != s[0][0]:\n",
    "                        while s and r > s[0][1]:\n",
    "                            heapq.heappop(s)\n",
    "                        rh = -s[0][0] if s else 0\n",
    "                        # 避免右端点重复\n",
    "                        if r == ans[-1][0]:\n",
    "                            ans[-1][1] = min(ans[-1][1], rh)\n",
    "                        else:\n",
    "                            ans.append([r, rh])\n",
    "                    cur = r\n",
    "            if not s or height > -s[0][0]:\n",
    "                # 避免左端点重复的问题\n",
    "                if ans and left == ans[-1][0]:\n",
    "                    ans[-1][1] = height\n",
    "                else:\n",
    "                    ans.append([left, height])\n",
    "            heapq.heappush(s, [-height, right])\n",
    "        while s:\n",
    "            rh, r = heapq.heappop(s)\n",
    "            if r >= cur:\n",
    "                if not s or rh != s[0][0]:\n",
    "                    while s and r > s[0][1]:\n",
    "                        heapq.heappop(s)\n",
    "                    rh = -s[0][0] if s else 0\n",
    "                    # 避免右端点重复\n",
    "                    if r == ans[-1][0]:\n",
    "                        ans[-1][1] = min(ans[-1][1], rh)\n",
    "                    else:\n",
    "                        ans.append([r, rh])\n",
    "                cur = r\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(buildings)\n",
    "        # 1、分界点\n",
    "        boundaries = []\n",
    "        for start, end, height in buildings:\n",
    "            boundaries.append(start)\n",
    "            boundaries.append(end)\n",
    "        boundaries.sort()\n",
    "        \n",
    "        # 2、高度越大越在上\n",
    "        pq = []\n",
    "        ret = []\n",
    "        idx = 0 #扫描线\n",
    "        # 遍历到边界点，将无效区间删除，将有效区间保存，然后求最大值\n",
    "        for boundary in boundaries:\n",
    "            # 加入区间：区间左侧小于等于边界点，注意区间范围左闭右开\n",
    "            while idx < n and buildings[idx][0] <= boundary and buildings[idx][1] > boundary:\n",
    "                heapq.heappush(pq, [-buildings[idx][2], buildings[idx][1]])\n",
    "                idx += 1\n",
    "\n",
    "            # 淘汰区间：删除没有覆盖边界点的区间，注意区间范围左闭右开，注意堆中可能有其他没有被删除掉的区间，但是由于不在堆顶，故而不影响结果\n",
    "            while pq and pq[0][1] <= boundary:\n",
    "                heapq.heappop(pq)\n",
    "            maxn = -pq[0][0] if pq else 0 \n",
    "            \n",
    "            # 边界最值：相邻两个边界点对应的高度一致，只取第一个边界点。\n",
    "            if not ret or maxn != ret[-1][1]:\n",
    "                ret.append([boundary, maxn])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Building:\n",
    "    def __init__(self, right, height):\n",
    "        self.right = right\n",
    "        self.height = height\n",
    "    \n",
    "    def __lt__(self, other):\n",
    "        return self.height >= other.height\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        lines = []\n",
    "        for left, right, height in buildings:\n",
    "            lines.append(left)\n",
    "            lines.append(right)\n",
    "        lines = sorted(lines)\n",
    "        i = 0\n",
    "        pq = []\n",
    "        ans = []\n",
    "        for x in lines:\n",
    "            while i < len(buildings) and buildings[i][0] == x:\n",
    "                heapq.heappush(pq, Building(buildings[i][1], buildings[i][2]))\n",
    "                i += 1\n",
    "            while len(pq) > 0 and pq[0].right <= x:\n",
    "                heapq.heappop(pq)\n",
    "            if len(pq) == 0:\n",
    "                top = 0\n",
    "            else:\n",
    "                top = pq[0].height\n",
    "            if len(ans) == 0 or top != ans[-1][1]:\n",
    "                ans.append([x, top])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        changes = []\n",
    "        for left, right, height in buildings:\n",
    "            changes.append((left, -height))\n",
    "            changes.append((right, height))\n",
    "        changes.sort()\n",
    "        live = SortedList([0])\n",
    "        prev = 0\n",
    "        for x, h in changes:\n",
    "            if h < 0:\n",
    "                live.add(h)\n",
    "            else:\n",
    "                live.remove(-h)\n",
    "            curmax = -live[0]\n",
    "            if curmax != prev:\n",
    "                res.append([x, curmax])\n",
    "            prev = curmax\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: [[int]]) -> [[int]]:\n",
    "        if len(buildings) == 0:\n",
    "            return []\n",
    "\n",
    "        points = []\n",
    "        for l, r, h in buildings:\n",
    "            # 左端点通过负数高度来标识，同时适用于标准库中的小顶堆转换为大顶堆\n",
    "            points.append((l, -h, r))\n",
    "            points.append((r, h, r))\n",
    "\n",
    "        # 将扫描线中的关键点按照points的前两个元素x, y来排序\n",
    "        points.sort()\n",
    "\n",
    "        # 初始值，[0初始高度， float('inf')对应无穷右边界]\n",
    "        height_heap = [[0, float('inf')]]    \n",
    "        res = [[0, 0]]\n",
    "\n",
    "        for x, h, r in points:\n",
    "            # 关键点：清除扫过的高楼\n",
    "            while x >= height_heap[0][1]:\n",
    "                heapq.heappop(height_heap)\n",
    "\n",
    "            # 左端点入堆\n",
    "            if h < 0:\n",
    "                heapq.heappush(height_heap, [h, r])\n",
    "\n",
    "            # 如果当前最大高度变化，说明是天际线中的关键点\n",
    "            if res[-1][1] != -height_heap[0][0]:\n",
    "                res.append([x, -height_heap[0][0]])\n",
    "\n",
    "        return res[1:]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        import sortedcontainers\n",
    "        records=[]\n",
    "        for l,r,h in buildings:\n",
    "            records.append([l,-h])\n",
    "            records.append([r,h])\n",
    "        records.sort()\n",
    "\n",
    "        pre,score,ret=0,0,[]\n",
    "        q=sortedcontainers.SortedList([pre])\n",
    "        for point,height in records:\n",
    "            if height>0:\n",
    "                q.remove(height)\n",
    "            else:\n",
    "                q.add(-height)\n",
    "            cur=q[-1]\n",
    "            if cur!=pre:\n",
    "                pre=cur\n",
    "                ret.append([point,cur])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        heights=[]\n",
    "        for x,y,h in buildings:\n",
    "            heights.append((x,-h))\n",
    "            heights.append((y,h))\n",
    "        heights.sort(key=lambda x:(x[0],x[1]))\n",
    "        res=[]\n",
    "        handled=[0]\n",
    "        cur_max=pre_max=0\n",
    "        for x,y in heights:\n",
    "            if y<0:\n",
    "                handled.append(-y)\n",
    "            else:\n",
    "                handled.remove(y)\n",
    "            cur_max=max(handled)\n",
    "            if pre_max!=cur_max:\n",
    "                res.append([x,cur_max])\n",
    "                pre_max=cur_max\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: [[int]]) -> [[int]]:\n",
    "        if len(buildings) == 0:\n",
    "            return []\n",
    "        \n",
    "        heights = []\n",
    "        ans = [[0, 0]]\n",
    "        hr = [[0, float('inf')]]\n",
    "        for l, r, h in buildings:\n",
    "            heights.append([l, -h, r])\n",
    "            heights.append([r, h, r])\n",
    "        \n",
    "        heights.sort()\n",
    "\n",
    "        for l, h, r in heights:\n",
    "            while hr[0][1] <= l:\n",
    "                heapq.heappop(hr)\n",
    "\n",
    "            if h < 0:\n",
    "                heapq.heappush(hr, [h, r])\n",
    "\n",
    "            if -hr[0][0] != ans[-1][1]:\n",
    "                ans.append([l, -hr[0][0]])\n",
    "\n",
    "\n",
    "        return ans[1:]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        # 扫描线+优先队列\n",
    "        points = [] # 记录左右端点及对应高度\n",
    "        for building in buildings:\n",
    "            left, right, height = building[0], building[1], building[2]\n",
    "            points.append([left, -height])\n",
    "            points.append([right, height])\n",
    "        points.sort(key=lambda x:(x[0], x[1]))\n",
    "\n",
    "        prev = 0\n",
    "        max_heap = SortedList([prev])\n",
    "\n",
    "        ans = []\n",
    "        for point in points:\n",
    "            x, height = point[0], point[1]\n",
    "            if height < 0: # 左端点\n",
    "                max_heap.add(-height)\n",
    "            else:\n",
    "                max_heap.remove(height)\n",
    "            cur = max_heap[-1]\n",
    "            if prev != cur:\n",
    "                ans.append([x, cur])\n",
    "                prev = cur\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        def update(p, h): # 将之前的结点最大值都更新（覆盖掉）\n",
    "            while p > 0:\n",
    "                bit[p] = max(bit[p], h)\n",
    "                p -= p & -p\n",
    "        \n",
    "\n",
    "        def query(p): # 查询此结点之后的最大值(是否被覆盖掉)\n",
    "            ret = 0\n",
    "            while p <= len(bit):\n",
    "                ret = max(ret, bit[p])\n",
    "                p += p & -p\n",
    "            return ret\n",
    "        \n",
    "\n",
    "        res, ends, nodes = [], {}, []\n",
    "        for i, b in enumerate(buildings):\n",
    "            nodes.extend([(b[0], -1, -b[2]), (b[1], 1, -b[2])])\n",
    "            ends[nodes[-2]] = nodes[-1]\n",
    "        \n",
    "        bit = [0]*(len(nodes)+1)\n",
    "        nodes.sort()\n",
    "        idx = {nodes[i] : i for i in range(len(nodes))}\n",
    "        for i, p in enumerate(nodes):\n",
    "            if p[1] == -1: # 当前点为左节点的时候\n",
    "                # end = ends[p]\n",
    "                update(idx[ends[p]], -p[-1])\n",
    "            \n",
    "            h = query(i+1)\n",
    "            #print(f\"bit:{bit},i:{i},h:{h}\")\n",
    "            if not res or res[-1][1] != h:\n",
    "                if res and res[-1][0] == p[0]:\n",
    "                    res[-1][1] = h\n",
    "                else:\n",
    "                    res.append([p[0], h])\n",
    "            \n",
    "        return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
